'''
Created on 2014-4-4

@author: festony
'''






class MinimumSquare:
    def getMaxSquareSide(self, x, y):
        minx = min(x)
        maxx = max(x)
        miny = min(y)
        maxy = max(y)
        
        disx = maxx - minx
        disy = maxy - miny
        dis = max(disx, disy)
        return dis + 2
    
    def testSquareContainsKAtP(self, x, y, K, s, p):
        N = len(x)
        clbx = p[0]
        clby = p[1]
        crtx = clbx + s
        crty = clby + s
        c = 0
        for i in range(N):
            if x[i] > clbx and x[i] < crtx and y[i] > clby and y[i] < crty:
                c += 1
        return c >= K
    
    def testSquareContainsK(self, x, y, K, s):
        minx = min(x)
        maxx = max(x)
        miny = min(y)
        maxy = max(y)
        
        startp = [minx - 1, miny - 1]
        endp = [maxx + 1, maxy + 1]
        
        for ix in x:
            for iy in y:
                p = [ix - 1, iy - 1]
                if self.testSquareContainsKAtP(x, y, K, s, p):
                    return True
#                p = [ix - 1, iy - s + 1]
#                if self.testSquareContainsKAtP(x, y, K, s, p):
#                    return True
#                p = [ix - s + 1, iy - 1]
#                if self.testSquareContainsKAtP(x, y, K, s, p):
#                    return True
#                p = [ix - s + 1, iy - s + 1]
#                if self.testSquareContainsKAtP(x, y, K, s, p):
#                    return True
        
        return False
    
    def minArea(self, x, y, K):
        down = 2
        up = self.getMaxSquareSide(x, y)
        mid = (up + down) / 2
        while up - down > 1:
            if self.testSquareContainsK(x, y, K, mid):
                up = mid
                mid = (up + down) / 2
            else:
                down = mid
                mid = (up + down) / 2
        return up * up






















